package 剑指;

public class m19_正则表达式匹配 {

    public static boolean isMatch(String s, String p) {
        if(s == null || p == null) return false;
        else return coreMatch(s, 0, p, 0);
    }

    public static boolean coreMatch(String s, int sPos, String p, int pPos){
        if(sPos == s.length() && pPos == p.length()){
            // end
            return true;
        }
        if(pPos <= p.length()-1){
            // 未结束
            if(pPos < p.length()-1 && p.charAt(pPos+1) == '*'){
                if(sPos >= s.length()){
                    //  b*
                    return coreMatch(s, sPos, p, pPos+2);
                }
                if(p.charAt(pPos) == s.charAt(sPos) || p.charAt(pPos) == '.'){
                    // aaa a* || ab a*b
                    return (
                            coreMatch(s, sPos+1, p, pPos) ||
                                    coreMatch(s, sPos, p, pPos+2) ||
                                    coreMatch(s, sPos+1, p, pPos+2));
                }else {
                    // b a*
                    return coreMatch(s, sPos, p, pPos+2);
                }
            }
            if(sPos < s.length() && (s.charAt(sPos) == p.charAt(pPos) || p.charAt(pPos) == '.')){
                // a . || a a
                return coreMatch(s, sPos+1, p, pPos+1);
            }
        }
        return false;
    }

    public static void main(String[] args){
        System.out.println(isMatch("ab", ".*c"));
//        System.out.println(isMatch("bbbba", ".*a*a"));
    }
}
